home *** CD-ROM | disk | FTP | other *** search
/ Stone Design / Stone Design.iso / Stone_Friends / Wave / WavesWorld / Source / Libraries / tcl7.4b3 / regexp.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-01-10  |  29.0 KB  |  1,278 lines
  1. /*
  2.  * TclRegComp and TclRegExec -- TclRegSub is elsewhere
  3.  *
  4.  *    Copyright (c) 1986 by University of Toronto.
  5.  *    Written by Henry Spencer.  Not derived from licensed software.
  6.  *
  7.  *    Permission is granted to anyone to use this software for any
  8.  *    purpose on any computer system, and to redistribute it freely,
  9.  *    subject to the following restrictions:
  10.  *
  11.  *    1. The author is not responsible for the consequences of use of
  12.  *        this software, no matter how awful, even if they arise
  13.  *        from defects in it.
  14.  *
  15.  *    2. The origin of this software must not be misrepresented, either
  16.  *        by explicit claim or by omission.
  17.  *
  18.  *    3. Altered versions must be plainly marked as such, and must not
  19.  *        be misrepresented as being the original software.
  20.  *
  21.  * Beware that some of this code is subtly aware of the way operator
  22.  * precedence is structured in regular expressions.  Serious changes in
  23.  * regular-expression syntax might require a total rethink.
  24.  *
  25.  * *** NOTE: this code has been altered slightly for use in Tcl: ***
  26.  * *** 1. Use ckalloc and ckfree instead of  malloc and free.     ***
  27.  * *** 2. Add extra argument to regexp to specify the real     ***
  28.  * ***    start of the string separately from the start of the     ***
  29.  * ***    current search. This is needed to search for multiple     ***
  30.  * ***    matches within a string.                 ***
  31.  * *** 3. Names have been changed, e.g. from regcomp to         ***
  32.  * ***    TclRegComp, to avoid clashes with other          ***
  33.  * ***    regexp implementations used by applications.          ***
  34.  * *** 4. Added tclRegexpError declaration and TclRegError     ***
  35.  * ***      procedure.                         ***
  36.  * *** 4. Various lint-like things, such as casting arguments     ***
  37.  * ***      in procedure calls.                     ***
  38.  */
  39.  
  40. static char sccsid[] = "@(#) regexp.c 1.5 95/01/10 09:27:11";
  41.  
  42. #include "tclInt.h"
  43. #include "tclPort.h"
  44.  
  45. /*
  46.  * The variable below is set to NULL before invoking regexp functions
  47.  * and checked after those functions.  If an error occurred then TclRegError
  48.  * will set the variable to point to a (static) error message.  This
  49.  * mechanism unfortunately does not support multi-threading, but then
  50.  * neither does the rest of the regexp facilities.
  51.  */
  52.  
  53. char *tclRegexpError = NULL;
  54.  
  55. /*
  56.  * The "internal use only" fields in regexp.h are present to pass info from
  57.  * compile to execute that permits the execute phase to run lots faster on
  58.  * simple cases.  They are:
  59.  *
  60.  * regstart    char that must begin a match; '\0' if none obvious
  61.  * reganch    is the match anchored (at beginning-of-line only)?
  62.  * regmust    string (pointer into program) that match must include, or NULL
  63.  * regmlen    length of regmust string
  64.  *
  65.  * Regstart and reganch permit very fast decisions on suitable starting points
  66.  * for a match, cutting down the work a lot.  Regmust permits fast rejection
  67.  * of lines that cannot possibly match.  The regmust tests are costly enough
  68.  * that TclRegComp() supplies a regmust only if the r.e. contains something
  69.  * potentially expensive (at present, the only such thing detected is * or +
  70.  * at the start of the r.e., which can involve a lot of backup).  Regmlen is
  71.  * supplied because the test in TclRegExec() needs it and TclRegComp() is
  72.  * computing it anyway.
  73.  */
  74.  
  75. /*
  76.  * Structure for regexp "program".  This is essentially a linear encoding
  77.  * of a nondeterministic finite-state machine (aka syntax charts or
  78.  * "railroad normal form" in parsing technology).  Each node is an opcode
  79.  * plus a "next" pointer, possibly plus an operand.  "Next" pointers of
  80.  * all nodes except BRANCH implement concatenation; a "next" pointer with
  81.  * a BRANCH on both ends of it is connecting two alternatives.  (Here we
  82.  * have one of the subtle syntax dependencies:  an individual BRANCH (as
  83.  * opposed to a collection of them) is never concatenated with anything
  84.  * because of operator precedence.)  The operand of some types of node is
  85.  * a literal string; for others, it is a node leading into a sub-FSM.  In
  86.  * particular, the operand of a BRANCH node is the first node of the branch.
  87.  * (NB this is *not* a tree structure:  the tail of the branch connects
  88.  * to the thing following the set of BRANCHes.)  The opcodes are:
  89.  */
  90.  
  91. /* definition    number    opnd?    meaning */
  92. #define    END    0    /* no    End of program. */
  93. #define    BOL    1    /* no    Match "" at beginning of line. */
  94. #define    EOL    2    /* no    Match "" at end of line. */
  95. #define    ANY    3    /* no    Match any one character. */
  96. #define    ANYOF    4    /* str    Match any character in this string. */
  97. #define    ANYBUT    5    /* str    Match any character not in this string. */
  98. #define    BRANCH    6    /* node    Match this alternative, or the next... */
  99. #define    BACK    7    /* no    Match "", "next" ptr points backward. */
  100. #define    EXACTLY    8    /* str    Match this string. */
  101. #define    NOTHING    9    /* no    Match empty string. */
  102. #define    STAR    10    /* node    Match this (simple) thing 0 or more times. */
  103. #define    PLUS    11    /* node    Match this (simple) thing 1 or more times. */
  104. #define    OPEN    20    /* no    Mark this point in input as start of #n. */
  105.             /*    OPEN+1 is number 1, etc. */
  106. #define    CLOSE    30    /* no    Analogous to OPEN. */
  107.  
  108. /*
  109.  * Opcode notes:
  110.  *
  111.  * BRANCH    The set of branches constituting a single choice are hooked
  112.  *        together with their "next" pointers, since precedence prevents
  113.  *        anything being concatenated to any individual branch.  The
  114.  *        "next" pointer of the last BRANCH in a choice points to the
  115.  *        thing following the whole choice.  This is also where the
  116.  *        final "next" pointer of each individual branch points; each
  117.  *        branch starts with the operand node of a BRANCH node.
  118.  *
  119.  * BACK        Normal "next" pointers all implicitly point forward; BACK
  120.  *        exists to make loop structures possible.
  121.  *
  122.  * STAR,PLUS    '?', and complex '*' and '+', are implemented as circular
  123.  *        BRANCH structures using BACK.  Simple cases (one character
  124.  *        per match) are implemented with STAR and PLUS for speed
  125.  *        and to minimize recursive plunges.
  126.  *
  127.  * OPEN,CLOSE    ...are numbered at compile time.
  128.  */
  129.  
  130. /*
  131.  * A node is one char of opcode followed by two chars of "next" pointer.
  132.  * "Next" pointers are stored as two 8-bit pieces, high order first.  The
  133.  * value is a positive offset from the opcode of the node containing it.
  134.  * An operand, if any, simply follows the node.  (Note that much of the
  135.  * code generation knows about this implicit relationship.)
  136.  *
  137.  * Using two bytes for the "next" pointer is vast overkill for most things,
  138.  * but allows patterns to get big without disasters.
  139.  */
  140. #define    OP(p)    (*(p))
  141. #define    NEXT(p)    (((*((p)+1)&0377)<<8) + (*((p)+2)&0377))
  142. #define    OPERAND(p)    ((p) + 3)
  143.  
  144. /*
  145.  * See regmagic.h for one further detail of program structure.
  146.  */
  147.  
  148.  
  149. /*
  150.  * Utility definitions.
  151.  */
  152. #ifndef CHARBITS
  153. #define    UCHARAT(p)    ((int)*(unsigned char *)(p))
  154. #else
  155. #define    UCHARAT(p)    ((int)*(p)&CHARBITS)
  156. #endif
  157.  
  158. #define    FAIL(m)    { TclRegError(m); return(NULL); }
  159. #define    ISMULT(c)    ((c) == '*' || (c) == '+' || (c) == '?')
  160. #define    META    "^$.[()|?+*\\"
  161.  
  162. /*
  163.  * Flags to be passed up and down.
  164.  */
  165. #define    HASWIDTH    01    /* Known never to match null string. */
  166. #define    SIMPLE        02    /* Simple enough to be STAR/PLUS operand. */
  167. #define    SPSTART        04    /* Starts with * or +. */
  168. #define    WORST        0    /* Worst case. */
  169.  
  170. /*
  171.  * Global work variables for TclRegComp().
  172.  */
  173. static char *regparse;        /* Input-scan pointer. */
  174. static int regnpar;        /* () count. */
  175. static char regdummy;
  176. static char *regcode;        /* Code-emit pointer; ®dummy = don't. */
  177. static long regsize;        /* Code size. */
  178.  
  179. /*
  180.  * The first byte of the regexp internal "program" is actually this magic
  181.  * number; the start node begins in the second byte.
  182.  */
  183. #define    MAGIC    0234
  184.  
  185.  
  186. /*
  187.  * Forward declarations for TclRegComp()'s friends.
  188.  */
  189. #ifndef STATIC
  190. #define    STATIC    static
  191. #endif
  192. STATIC char *reg();
  193. STATIC char *regbranch();
  194. STATIC char *regpiece();
  195. STATIC char *regatom();
  196. STATIC char *regnode();
  197. STATIC char *regnext();
  198. STATIC void regc();
  199. STATIC void reginsert();
  200. STATIC void regtail();
  201. STATIC void regoptail();
  202. #ifdef STRCSPN
  203. STATIC int strcspn();
  204. #endif
  205.  
  206. /*
  207.  - TclRegComp - compile a regular expression into internal code
  208.  *
  209.  * We can't allocate space until we know how big the compiled form will be,
  210.  * but we can't compile it (and thus know how big it is) until we've got a
  211.  * place to put the code.  So we cheat:  we compile it twice, once with code
  212.  * generation turned off and size counting turned on, and once "for real".
  213.  * This also means that we don't allocate space until we are sure that the
  214.  * thing really will compile successfully, and we never have to move the
  215.  * code and thus invalidate pointers into it.  (Note that it has to be in
  216.  * one piece because free() must be able to free it all.)
  217.  *
  218.  * Beware that the optimization-preparation code in here knows about some
  219.  * of the structure of the compiled regexp.
  220.  */
  221. regexp *
  222. TclRegComp(exp)
  223. char *exp;
  224. {
  225.     register regexp *r;
  226.     register char *scan;
  227.     register char *longest;
  228.     register int len;
  229.     int flags;
  230.  
  231.     if (exp == NULL)
  232.         FAIL("NULL argument");
  233.  
  234.     /* First pass: determine size, legality. */
  235.     regparse = exp;
  236.     regnpar = 1;
  237.     regsize = 0L;
  238.     regcode = ®dummy;
  239.     regc(MAGIC);
  240.     if (reg(0, &flags) == NULL)
  241.         return(NULL);
  242.  
  243.     /* Small enough for pointer-storage convention? */
  244.     if (regsize >= 32767L)        /* Probably could be 65535L. */
  245.         FAIL("regexp too big");
  246.  
  247.     /* Allocate space. */
  248.     r = (regexp *)ckalloc(sizeof(regexp) + (unsigned)regsize);
  249.     if (r == NULL)
  250.         FAIL("out of space");
  251.  
  252.     /* Second pass: emit code. */
  253.     regparse = exp;
  254.     regnpar = 1;
  255.     regcode = r->program;
  256.     regc(MAGIC);
  257.     if (reg(0, &flags) == NULL)
  258.         return(NULL);
  259.  
  260.     /* Dig out information for optimizations. */
  261.     r->regstart = '\0';    /* Worst-case defaults. */
  262.     r->reganch = 0;
  263.     r->regmust = NULL;
  264.     r->regmlen = 0;
  265.     scan = r->program+1;            /* First BRANCH. */
  266.     if (OP(regnext(scan)) == END) {        /* Only one top-level choice. */
  267.         scan = OPERAND(scan);
  268.  
  269.         /* Starting-point info. */
  270.         if (OP(scan) == EXACTLY)
  271.             r->regstart = *OPERAND(scan);
  272.         else if (OP(scan) == BOL)
  273.             r->reganch++;
  274.  
  275.         /*
  276.          * If there's something expensive in the r.e., find the
  277.          * longest literal string that must appear and make it the
  278.          * regmust.  Resolve ties in favor of later strings, since
  279.          * the regstart check works with the beginning of the r.e.
  280.          * and avoiding duplication strengthens checking.  Not a
  281.          * strong reason, but sufficient in the absence of others.
  282.          */
  283.         if (flags&SPSTART) {
  284.             longest = NULL;
  285.             len = 0;
  286.             for (; scan != NULL; scan = regnext(scan))
  287.                 if (OP(scan) == EXACTLY && ((int) strlen(OPERAND(scan))) >= len) {
  288.                     longest = OPERAND(scan);
  289.                     len = strlen(OPERAND(scan));
  290.                 }
  291.             r->regmust = longest;
  292.             r->regmlen = len;
  293.         }
  294.     }
  295.  
  296.     return(r);
  297. }
  298.  
  299. /*
  300.  - reg - regular expression, i.e. main body or parenthesized thing
  301.  *
  302.  * Caller must absorb opening parenthesis.
  303.  *
  304.  * Combining parenthesis handling with the base level of regular expression
  305.  * is a trifle forced, but the need to tie the tails of the branches to what
  306.  * follows makes it hard to avoid.
  307.  */
  308. static char *
  309. reg(paren, flagp)
  310. int paren;            /* Parenthesized? */
  311. int *flagp;
  312. {
  313.     register char *ret;
  314.     register char *br;
  315.     register char *ender;
  316.     register int parno = 0;
  317.     int flags;
  318.  
  319.     *flagp = HASWIDTH;    /* Tentatively. */
  320.  
  321.     /* Make an OPEN node, if parenthesized. */
  322.     if (paren) {
  323.         if (regnpar >= NSUBEXP)
  324.             FAIL("too many ()");
  325.         parno = regnpar;
  326.         regnpar++;
  327.         ret = regnode(OPEN+parno);
  328.     } else
  329.         ret = NULL;
  330.  
  331.     /* Pick up the branches, linking them together. */
  332.     br = regbranch(&flags);
  333.     if (br == NULL)
  334.         return(NULL);
  335.     if (ret != NULL)
  336.         regtail(ret, br);    /* OPEN -> first. */
  337.     else
  338.         ret = br;
  339.     if (!(flags&HASWIDTH))
  340.         *flagp &= ~HASWIDTH;
  341.     *flagp |= flags&SPSTART;
  342.     while (*regparse == '|') {
  343.         regparse++;
  344.         br = regbranch(&flags);
  345.         if (br == NULL)
  346.             return(NULL);
  347.         regtail(ret, br);    /* BRANCH -> BRANCH. */
  348.         if (!(flags&HASWIDTH))
  349.             *flagp &= ~HASWIDTH;
  350.         *flagp |= flags&SPSTART;
  351.     }
  352.  
  353.     /* Make a closing node, and hook it on the end. */
  354.     ender = regnode((paren) ? CLOSE+parno : END);    
  355.     regtail(ret, ender);
  356.  
  357.     /* Hook the tails of the branches to the closing node. */
  358.     for (br = ret; br != NULL; br = regnext(br))
  359.         regoptail(br, ender);
  360.  
  361.     /* Check for proper termination. */
  362.     if (paren && *regparse++ != ')') {
  363.         FAIL("unmatched ()");
  364.     } else if (!paren && *regparse != '\0') {
  365.         if (*regparse == ')') {
  366.             FAIL("unmatched ()");
  367.         } else
  368.             FAIL("junk on end");    /* "Can't happen". */
  369.         /* NOTREACHED */
  370.     }
  371.  
  372.     return(ret);
  373. }
  374.  
  375. /*
  376.  - regbranch - one alternative of an | operator
  377.  *
  378.  * Implements the concatenation operator.
  379.  */
  380. static char *
  381. regbranch(flagp)
  382. int *flagp;
  383. {
  384.     register char *ret;
  385.     register char *chain;
  386.     register char *latest;
  387.     int flags;
  388.  
  389.     *flagp = WORST;        /* Tentatively. */
  390.  
  391.     ret = regnode(BRANCH);
  392.     chain = NULL;
  393.     while (*regparse != '\0' && *regparse != '|' && *regparse != ')') {
  394.         latest = regpiece(&flags);
  395.         if (latest == NULL)
  396.             return(NULL);
  397.         *flagp |= flags&HASWIDTH;
  398.         if (chain == NULL)    /* First piece. */
  399.             *flagp |= flags&SPSTART;
  400.         else
  401.             regtail(chain, latest);
  402.         chain = latest;
  403.     }
  404.     if (chain == NULL)    /* Loop ran zero times. */
  405.         (void) regnode(NOTHING);
  406.  
  407.     return(ret);
  408. }
  409.  
  410. /*
  411.  - regpiece - something followed by possible [*+?]
  412.  *
  413.  * Note that the branching code sequences used for ? and the general cases
  414.  * of * and + are somewhat optimized:  they use the same NOTHING node as
  415.  * both the endmarker for their branch list and the body of the last branch.
  416.  * It might seem that this node could be dispensed with entirely, but the
  417.  * endmarker role is not redundant.
  418.  */
  419. static char *
  420. regpiece(flagp)
  421. int *flagp;
  422. {
  423.     register char *ret;
  424.     register char op;
  425.     register char *next;
  426.     int flags;
  427.  
  428.     ret = regatom(&flags);
  429.     if (ret == NULL)
  430.         return(NULL);
  431.  
  432.     op = *regparse;
  433.     if (!ISMULT(op)) {
  434.         *flagp = flags;
  435.         return(ret);
  436.     }
  437.  
  438.     if (!(flags&HASWIDTH) && op != '?')
  439.         FAIL("*+ operand could be empty");
  440.     *flagp = (op != '+') ? (WORST|SPSTART) : (WORST|HASWIDTH);
  441.  
  442.     if (op == '*' && (flags&SIMPLE))
  443.         reginsert(STAR, ret);
  444.     else if (op == '*') {
  445.         /* Emit x* as (x&|), where & means "self". */
  446.         reginsert(BRANCH, ret);            /* Either x */
  447.         regoptail(ret, regnode(BACK));        /* and loop */
  448.         regoptail(ret, ret);            /* back */
  449.         regtail(ret, regnode(BRANCH));        /* or */
  450.         regtail(ret, regnode(NOTHING));        /* null. */
  451.     } else if (op == '+' && (flags&SIMPLE))
  452.         reginsert(PLUS, ret);
  453.     else if (op == '+') {
  454.         /* Emit x+ as x(&|), where & means "self". */
  455.         next = regnode(BRANCH);            /* Either */
  456.         regtail(ret, next);
  457.         regtail(regnode(BACK), ret);        /* loop back */
  458.         regtail(next, regnode(BRANCH));        /* or */
  459.         regtail(ret, regnode(NOTHING));        /* null. */
  460.     } else if (op == '?') {
  461.         /* Emit x? as (x|) */
  462.         reginsert(BRANCH, ret);            /* Either x */
  463.         regtail(ret, regnode(BRANCH));        /* or */
  464.         next = regnode(NOTHING);        /* null. */
  465.         regtail(ret, next);
  466.         regoptail(ret, next);
  467.     }
  468.     regparse++;
  469.     if (ISMULT(*regparse))
  470.         FAIL("nested *?+");
  471.  
  472.     return(ret);
  473. }
  474.  
  475. /*
  476.  - regatom - the lowest level
  477.  *
  478.  * Optimization:  gobbles an entire sequence of ordinary characters so that
  479.  * it can turn them into a single node, which is smaller to store and
  480.  * faster to run.  Backslashed characters are exceptions, each becoming a
  481.  * separate node; the code is simpler that way and it's not worth fixing.
  482.  */
  483. static char *
  484. regatom(flagp)
  485. int *flagp;
  486. {
  487.     register char *ret;
  488.     int flags;
  489.  
  490.     *flagp = WORST;        /* Tentatively. */
  491.  
  492.     switch (*regparse++) {
  493.     case '^':
  494.         ret = regnode(BOL);
  495.         break;
  496.     case '$':
  497.         ret = regnode(EOL);
  498.         break;
  499.     case '.':
  500.         ret = regnode(ANY);
  501.         *flagp |= HASWIDTH|SIMPLE;
  502.         break;
  503.     case '[': {
  504.             register int clss;
  505.             register int classend;
  506.  
  507.             if (*regparse == '^') {    /* Complement of range. */
  508.                 ret = regnode(ANYBUT);
  509.                 regparse++;
  510.             } else
  511.                 ret = regnode(ANYOF);
  512.             if (*regparse == ']' || *regparse == '-')
  513.                 regc(*regparse++);
  514.             while (*regparse != '\0' && *regparse != ']') {
  515.                 if (*regparse == '-') {
  516.                     regparse++;
  517.                     if (*regparse == ']' || *regparse == '\0')
  518.                         regc('-');
  519.                     else {
  520.                         clss = UCHARAT(regparse-2)+1;
  521.                         classend = UCHARAT(regparse);
  522.                         if (clss > classend+1)
  523.                             FAIL("invalid [] range");
  524.                         for (; clss <= classend; clss++)
  525.                             regc(clss);
  526.                         regparse++;
  527.                     }
  528.                 } else
  529.                     regc(*regparse++);
  530.             }
  531.             regc('\0');
  532.             if (*regparse != ']')
  533.                 FAIL("unmatched []");
  534.             regparse++;
  535.             *flagp |= HASWIDTH|SIMPLE;
  536.         }
  537.         break;
  538.     case '(':
  539.         ret = reg(1, &flags);
  540.         if (ret == NULL)
  541.             return(NULL);
  542.         *flagp |= flags&(HASWIDTH|SPSTART);
  543.         break;
  544.     case '\0':
  545.     case '|':
  546.     case ')':
  547.         FAIL("internal urp");    /* Supposed to be caught earlier. */
  548.         /* NOTREACHED */
  549.         break;
  550.     case '?':
  551.     case '+':
  552.     case '*':
  553.         FAIL("?+* follows nothing");
  554.         /* NOTREACHED */
  555.         break;
  556.     case '\\':
  557.         if (*regparse == '\0')
  558.             FAIL("trailing \\");
  559.         ret = regnode(EXACTLY);
  560.         regc(*regparse++);
  561.         regc('\0');
  562.         *flagp |= HASWIDTH|SIMPLE;
  563.         break;
  564.     default: {
  565.             register int len;
  566.             register char ender;
  567.  
  568.             regparse--;
  569.             len = strcspn(regparse, META);
  570.             if (len <= 0)
  571.                 FAIL("internal disaster");
  572.             ender = *(regparse+len);
  573.             if (len > 1 && ISMULT(ender))
  574.                 len--;        /* Back off clear of ?+* operand. */
  575.             *flagp |= HASWIDTH;
  576.             if (len == 1)
  577.                 *flagp |= SIMPLE;
  578.             ret = regnode(EXACTLY);
  579.             while (len > 0) {
  580.                 regc(*regparse++);
  581.                 len--;
  582.             }
  583.             regc('\0');
  584.         }
  585.         break;
  586.     }
  587.  
  588.     return(ret);
  589. }
  590.  
  591. /*
  592.  - regnode - emit a node
  593.  */
  594. static char *            /* Location. */
  595. regnode(op)
  596. char op;
  597. {
  598.     register char *ret;
  599.     register char *ptr;
  600.  
  601.     ret = regcode;
  602.     if (ret == ®dummy) {
  603.         regsize += 3;
  604.         return(ret);
  605.     }
  606.  
  607.     ptr = ret;
  608.     *ptr++ = op;
  609.     *ptr++ = '\0';        /* Null "next" pointer. */
  610.     *ptr++ = '\0';
  611.     regcode = ptr;
  612.  
  613.     return(ret);
  614. }
  615.  
  616. /*
  617.  - regc - emit (if appropriate) a byte of code
  618.  */
  619. static void
  620. regc(b)
  621. char b;
  622. {
  623.     if (regcode != ®dummy)
  624.         *regcode++ = b;
  625.     else
  626.         regsize++;
  627. }
  628.  
  629. /*
  630.  - reginsert - insert an operator in front of already-emitted operand
  631.  *
  632.  * Means relocating the operand.
  633.  */
  634. static void
  635. reginsert(op, opnd)
  636. char op;
  637. char *opnd;
  638. {
  639.     register char *src;
  640.     register char *dst;
  641.     register char *place;
  642.  
  643.     if (regcode == ®dummy) {
  644.         regsize += 3;
  645.         return;
  646.     }
  647.  
  648.     src = regcode;
  649.     regcode += 3;
  650.     dst = regcode;
  651.     while (src > opnd)
  652.         *--dst = *--src;
  653.  
  654.     place = opnd;        /* Op node, where operand used to be. */
  655.     *place++ = op;
  656.     *place++ = '\0';
  657.     *place++ = '\0';
  658. }
  659.  
  660. /*
  661.  - regtail - set the next-pointer at the end of a node chain
  662.  */
  663. static void
  664. regtail(p, val)
  665. char *p;
  666. char *val;
  667. {
  668.     register char *scan;
  669.     register char *temp;
  670.     register int offset;
  671.  
  672.     if (p == ®dummy)
  673.         return;
  674.  
  675.     /* Find last node. */
  676.     scan = p;
  677.     for (;;) {
  678.         temp = regnext(scan);
  679.         if (temp == NULL)
  680.             break;
  681.         scan = temp;
  682.     }
  683.  
  684.     if (OP(scan) == BACK)
  685.         offset = scan - val;
  686.     else
  687.         offset = val - scan;
  688.     *(scan+1) = (offset>>8)&0377;
  689.     *(scan+2) = offset&0377;
  690. }
  691.  
  692. /*
  693.  - regoptail - regtail on operand of first argument; nop if operandless
  694.  */
  695. static void
  696. regoptail(p, val)
  697. char *p;
  698. char *val;
  699. {
  700.     /* "Operandless" and "op != BRANCH" are synonymous in practice. */
  701.     if (p == NULL || p == ®dummy || OP(p) != BRANCH)
  702.         return;
  703.     regtail(OPERAND(p), val);
  704. }
  705.  
  706. /*
  707.  * TclRegExec and friends
  708.  */
  709.  
  710. /*
  711.  * Global work variables for TclRegExec().
  712.  */
  713. static char *reginput;        /* String-input pointer. */
  714. static char *regbol;        /* Beginning of input, for ^ check. */
  715. static char **regstartp;    /* Pointer to startp array. */
  716. static char **regendp;        /* Ditto for endp. */
  717.  
  718. /*
  719.  * Forwards.
  720.  */
  721. STATIC int regtry();
  722. STATIC int regmatch();
  723. STATIC int regrepeat();
  724.  
  725. #ifdef DEBUG
  726. int regnarrate = 0;
  727. void regdump();
  728. STATIC char *regprop();
  729. #endif
  730.  
  731. /*
  732.  - TclRegExec - match a regexp against a string
  733.  */
  734. int
  735. TclRegExec(prog, string, start)
  736. register regexp *prog;
  737. register char *string;
  738. char *start;
  739. {
  740.     register char *s;
  741.  
  742.     /* Be paranoid... */
  743.     if (prog == NULL || string == NULL) {
  744.         TclRegError("NULL parameter");
  745.         return(0);
  746.     }
  747.  
  748.     /* Check validity of program. */
  749.     if (UCHARAT(prog->program) != MAGIC) {
  750.         TclRegError("corrupted program");
  751.         return(0);
  752.     }
  753.  
  754.     /* If there is a "must appear" string, look for it. */
  755.     if (prog->regmust != NULL) {
  756.         s = string;
  757.         while ((s = strchr(s, prog->regmust[0])) != NULL) {
  758.             if (strncmp(s, prog->regmust, (size_t) prog->regmlen)
  759.                 == 0)
  760.                 break;    /* Found it. */
  761.             s++;
  762.         }
  763.         if (s == NULL)    /* Not present. */
  764.             return(0);
  765.     }
  766.  
  767.     /* Mark beginning of line for ^ . */
  768.     regbol = start;
  769.  
  770.     /* Simplest case:  anchored match need be tried only once. */
  771.     if (prog->reganch)
  772.         return(regtry(prog, string));
  773.  
  774.     /* Messy cases:  unanchored match. */
  775.     s = string;
  776.     if (prog->regstart != '\0')
  777.         /* We know what char it must start with. */
  778.         while ((s = strchr(s, prog->regstart)) != NULL) {
  779.             if (regtry(prog, s))
  780.                 return(1);
  781.             s++;
  782.         }
  783.     else
  784.         /* We don't -- general case. */
  785.         do {
  786.             if (regtry(prog, s))
  787.                 return(1);
  788.         } while (*s++ != '\0');
  789.  
  790.     /* Failure. */
  791.     return(0);
  792. }
  793.  
  794. /*
  795.  - regtry - try match at specific point
  796.  */
  797. static int            /* 0 failure, 1 success */
  798. regtry(prog, string)
  799. regexp *prog;
  800. char *string;
  801. {
  802.     register int i;
  803.     register char **sp;
  804.     register char **ep;
  805.  
  806.     reginput = string;
  807.     regstartp = prog->startp;
  808.     regendp = prog->endp;
  809.  
  810.     sp = prog->startp;
  811.     ep = prog->endp;
  812.     for (i = NSUBEXP; i > 0; i--) {
  813.         *sp++ = NULL;
  814.         *ep++ = NULL;
  815.     }
  816.     if (regmatch(prog->program + 1)) {
  817.         prog->startp[0] = string;
  818.         prog->endp[0] = reginput;
  819.         return(1);
  820.     } else
  821.         return(0);
  822. }
  823.  
  824. /*
  825.  - regmatch - main matching routine
  826.  *
  827.  * Conceptually the strategy is simple:  check to see whether the current
  828.  * node matches, call self recursively to see whether the rest matches,
  829.  * and then act accordingly.  In practice we make some effort to avoid
  830.  * recursion, in particular by going through "ordinary" nodes (that don't
  831.  * need to know whether the rest of the match failed) by a loop instead of
  832.  * by recursion.
  833.  */
  834. static int            /* 0 failure, 1 success */
  835. regmatch(prog)
  836. char *prog;
  837. {
  838.     register char *scan;    /* Current node. */
  839.     char *next;        /* Next node. */
  840.  
  841.     scan = prog;
  842. #ifdef DEBUG
  843.     if (scan != NULL && regnarrate)
  844.         fprintf(stderr, "%s(\n", regprop(scan));
  845. #endif
  846.     while (scan != NULL) {
  847. #ifdef DEBUG
  848.         if (regnarrate)
  849.             fprintf(stderr, "%s...\n", regprop(scan));
  850. #endif
  851.         next = regnext(scan);
  852.  
  853.         switch (OP(scan)) {
  854.         case BOL:
  855.             if (reginput != regbol)
  856.                 return(0);
  857.             break;
  858.         case EOL:
  859.             if (*reginput != '\0')
  860.                 return(0);
  861.             break;
  862.         case ANY:
  863.             if (*reginput == '\0')
  864.                 return(0);
  865.             reginput++;
  866.             break;
  867.         case EXACTLY: {
  868.                 register int len;
  869.                 register char *opnd;
  870.  
  871.                 opnd = OPERAND(scan);
  872.                 /* Inline the first character, for speed. */
  873.                 if (*opnd != *reginput)
  874.                     return(0);
  875.                 len = strlen(opnd);
  876.                 if (len > 1 && strncmp(opnd, reginput, (size_t) len) != 0)
  877.                     return(0);
  878.                 reginput += len;
  879.             }
  880.             break;
  881.         case ANYOF:
  882.              if (*reginput == '\0' || strchr(OPERAND(scan), *reginput) == NULL)
  883.                 return(0);
  884.             reginput++;
  885.             break;
  886.         case ANYBUT:
  887.              if (*reginput == '\0' || strchr(OPERAND(scan), *reginput) != NULL)
  888.                 return(0);
  889.             reginput++;
  890.             break;
  891.         case NOTHING:
  892.             break;
  893.         case BACK:
  894.             break;
  895.         case OPEN+1:
  896.         case OPEN+2:
  897.         case OPEN+3:
  898.         case OPEN+4:
  899.         case OPEN+5:
  900.         case OPEN+6:
  901.         case OPEN+7:
  902.         case OPEN+8:
  903.         case OPEN+9: {
  904.                 register int no;
  905.                 register char *save;
  906.  
  907.                 no = OP(scan) - OPEN;
  908.                 save = reginput;
  909.  
  910.                 if (regmatch(next)) {
  911.                     /*
  912.                      * Don't set startp if some later
  913.                      * invocation of the same parentheses
  914.                      * already has.
  915.                      */
  916.                     if (regstartp[no] == NULL)
  917.                         regstartp[no] = save;
  918.                     return(1);
  919.                 } else
  920.                     return(0);
  921.             }
  922.             /* NOTREACHED */
  923.             break;
  924.         case CLOSE+1:
  925.         case CLOSE+2:
  926.         case CLOSE+3:
  927.         case CLOSE+4:
  928.         case CLOSE+5:
  929.         case CLOSE+6:
  930.         case CLOSE+7:
  931.         case CLOSE+8:
  932.         case CLOSE+9: {
  933.                 register int no;
  934.                 register char *save;
  935.  
  936.                 no = OP(scan) - CLOSE;
  937.                 save = reginput;
  938.  
  939.                 if (regmatch(next)) {
  940.                     /*
  941.                      * Don't set endp if some later
  942.                      * invocation of the same parentheses
  943.                      * already has.
  944.                      */
  945.                     if (regendp[no] == NULL)
  946.                         regendp[no] = save;
  947.                     return(1);
  948.                 } else
  949.                     return(0);
  950.             }
  951.             /* NOTREACHED */
  952.             break;
  953.         case BRANCH: {
  954.                 register char *save;
  955.  
  956.                 if (OP(next) != BRANCH)        /* No choice. */
  957.                     next = OPERAND(scan);    /* Avoid recursion. */
  958.                 else {
  959.                     do {
  960.                         save = reginput;
  961.                         if (regmatch(OPERAND(scan)))
  962.                             return(1);
  963.                         reginput = save;
  964.                         scan = regnext(scan);
  965.                     } while (scan != NULL && OP(scan) == BRANCH);
  966.                     return(0);
  967.                     /* NOTREACHED */
  968.                 }
  969.             }
  970.             /* NOTREACHED */
  971.             break;
  972.         case STAR:
  973.         case PLUS: {
  974.                 register char nextch;
  975.                 register int no;
  976.                 register char *save;
  977.                 register int min;
  978.  
  979.                 /*
  980.                  * Lookahead to avoid useless match attempts
  981.                  * when we know what character comes next.
  982.                  */
  983.                 nextch = '\0';
  984.                 if (OP(next) == EXACTLY)
  985.                     nextch = *OPERAND(next);
  986.                 min = (OP(scan) == STAR) ? 0 : 1;
  987.                 save = reginput;
  988.                 no = regrepeat(OPERAND(scan));
  989.                 while (no >= min) {
  990.                     /* If it could work, try it. */
  991.                     if (nextch == '\0' || *reginput == nextch)
  992.                         if (regmatch(next))
  993.                             return(1);
  994.                     /* Couldn't or didn't -- back up. */
  995.                     no--;
  996.                     reginput = save + no;
  997.                 }
  998.                 return(0);
  999.             }
  1000.             /* NOTREACHED */
  1001.             break;
  1002.         case END:
  1003.             return(1);    /* Success! */
  1004.             /* NOTREACHED */
  1005.             break;
  1006.         default:
  1007.             TclRegError("memory corruption");
  1008.             return(0);
  1009.             /* NOTREACHED */
  1010.             break;
  1011.         }
  1012.  
  1013.         scan = next;
  1014.     }
  1015.  
  1016.     /*
  1017.      * We get here only if there's trouble -- normally "case END" is
  1018.      * the terminating point.
  1019.      */
  1020.     TclRegError("corrupted pointers");
  1021.     return(0);
  1022. }
  1023.  
  1024. /*
  1025.  - regrepeat - repeatedly match something simple, report how many
  1026.  */
  1027. static int
  1028. regrepeat(p)
  1029. char *p;
  1030. {
  1031.     register int count = 0;
  1032.     register char *scan;
  1033.     register char *opnd;
  1034.  
  1035.     scan = reginput;
  1036.     opnd = OPERAND(p);
  1037.     switch (OP(p)) {
  1038.     case ANY:
  1039.         count = strlen(scan);
  1040.         scan += count;
  1041.         break;
  1042.     case EXACTLY:
  1043.         while (*opnd == *scan) {
  1044.             count++;
  1045.             scan++;
  1046.         }
  1047.         break;
  1048.     case ANYOF:
  1049.         while (*scan != '\0' && strchr(opnd, *scan) != NULL) {
  1050.             count++;
  1051.             scan++;
  1052.         }
  1053.         break;
  1054.     case ANYBUT:
  1055.         while (*scan != '\0' && strchr(opnd, *scan) == NULL) {
  1056.             count++;
  1057.             scan++;
  1058.         }
  1059.         break;
  1060.     default:        /* Oh dear.  Called inappropriately. */
  1061.         TclRegError("internal foulup");
  1062.         count = 0;    /* Best compromise. */
  1063.         break;
  1064.     }
  1065.     reginput = scan;
  1066.  
  1067.     return(count);
  1068. }
  1069.  
  1070. /*
  1071.  - regnext - dig the "next" pointer out of a node
  1072.  */
  1073. static char *
  1074. regnext(p)
  1075. register char *p;
  1076. {
  1077.     register int offset;
  1078.  
  1079.     if (p == ®dummy)
  1080.         return(NULL);
  1081.  
  1082.     offset = NEXT(p);
  1083.     if (offset == 0)
  1084.         return(NULL);
  1085.  
  1086.     if (OP(p) == BACK)
  1087.         return(p-offset);
  1088.     else
  1089.         return(p+offset);
  1090. }
  1091.  
  1092. #ifdef DEBUG
  1093.  
  1094. STATIC char *regprop();
  1095.  
  1096. /*
  1097.  - regdump - dump a regexp onto stdout in vaguely comprehensible form
  1098.  */
  1099. void
  1100. regdump(r)
  1101. regexp *r;
  1102. {
  1103.     register char *s;
  1104.     register char op = EXACTLY;    /* Arbitrary non-END op. */
  1105.     register char *next;
  1106.  
  1107.  
  1108.     s = r->program + 1;
  1109.     while (op != END) {    /* While that wasn't END last time... */
  1110.         op = OP(s);
  1111.         printf("%2d%s", s-r->program, regprop(s));    /* Where, what. */
  1112.         next = regnext(s);
  1113.         if (next == NULL)        /* Next ptr. */
  1114.             printf("(0)");
  1115.         else 
  1116.             printf("(%d)", (s-r->program)+(next-s));
  1117.         s += 3;
  1118.         if (op == ANYOF || op == ANYBUT || op == EXACTLY) {
  1119.             /* Literal string, where present. */
  1120.             while (*s != '\0') {
  1121.                 putchar(*s);
  1122.                 s++;
  1123.             }
  1124.             s++;
  1125.         }
  1126.         putchar('\n');
  1127.     }
  1128.  
  1129.     /* Header fields of interest. */
  1130.     if (r->regstart != '\0')
  1131.         printf("start `%c' ", r->regstart);
  1132.     if (r->reganch)
  1133.         printf("anchored ");
  1134.     if (r->regmust != NULL)
  1135.         printf("must have \"%s\"", r->regmust);
  1136.     printf("\n");
  1137. }
  1138.  
  1139. /*
  1140.  - regprop - printable representation of opcode
  1141.  */
  1142. static char *
  1143. regprop(op)
  1144. char *op;
  1145. {
  1146.     register char *p;
  1147.     static char buf[50];
  1148.  
  1149.     (void) strcpy(buf, ":");
  1150.  
  1151.     switch (OP(op)) {
  1152.     case BOL:
  1153.         p = "BOL";
  1154.         break;
  1155.     case EOL:
  1156.         p = "EOL";
  1157.         break;
  1158.     case ANY:
  1159.         p = "ANY";
  1160.         break;
  1161.     case ANYOF:
  1162.         p = "ANYOF";
  1163.         break;
  1164.     case ANYBUT:
  1165.         p = "ANYBUT";
  1166.         break;
  1167.     case BRANCH:
  1168.         p = "BRANCH";
  1169.         break;
  1170.     case EXACTLY:
  1171.         p = "EXACTLY";
  1172.         break;
  1173.     case NOTHING:
  1174.         p = "NOTHING";
  1175.         break;
  1176.     case BACK:
  1177.         p = "BACK";
  1178.         break;
  1179.     case END:
  1180.         p = "END";
  1181.         break;
  1182.     case OPEN+1:
  1183.     case OPEN+2:
  1184.     case OPEN+3:
  1185.     case OPEN+4:
  1186.     case OPEN+5:
  1187.     case OPEN+6:
  1188.     case OPEN+7:
  1189.     case OPEN+8:
  1190.     case OPEN+9:
  1191.         sprintf(buf+strlen(buf), "OPEN%d", OP(op)-OPEN);
  1192.         p = NULL;
  1193.         break;
  1194.     case CLOSE+1:
  1195.     case CLOSE+2:
  1196.     case CLOSE+3:
  1197.     case CLOSE+4:
  1198.     case CLOSE+5:
  1199.     case CLOSE+6:
  1200.     case CLOSE+7:
  1201.     case CLOSE+8:
  1202.     case CLOSE+9:
  1203.         sprintf(buf+strlen(buf), "CLOSE%d", OP(op)-CLOSE);
  1204.         p = NULL;
  1205.         break;
  1206.     case STAR:
  1207.         p = "STAR";
  1208.         break;
  1209.     case PLUS:
  1210.         p = "PLUS";
  1211.         break;
  1212.     default:
  1213.         TclRegError("corrupted opcode");
  1214.         break;
  1215.     }
  1216.     if (p != NULL)
  1217.         (void) strcat(buf, p);
  1218.     return(buf);
  1219. }
  1220. #endif
  1221.  
  1222. /*
  1223.  * The following is provided for those people who do not have strcspn() in
  1224.  * their C libraries.  They should get off their butts and do something
  1225.  * about it; at least one public-domain implementation of those (highly
  1226.  * useful) string routines has been published on Usenet.
  1227.  */
  1228. #ifdef STRCSPN
  1229. /*
  1230.  * strcspn - find length of initial segment of s1 consisting entirely
  1231.  * of characters not from s2
  1232.  */
  1233.  
  1234. static int
  1235. strcspn(s1, s2)
  1236. char *s1;
  1237. char *s2;
  1238. {
  1239.     register char *scan1;
  1240.     register char *scan2;
  1241.     register int count;
  1242.  
  1243.     count = 0;
  1244.     for (scan1 = s1; *scan1 != '\0'; scan1++) {
  1245.         for (scan2 = s2; *scan2 != '\0';)    /* ++ moved down. */
  1246.             if (*scan1 == *scan2++)
  1247.                 return(count);
  1248.         count++;
  1249.     }
  1250.     return(count);
  1251. }
  1252. #endif
  1253.  
  1254. /*
  1255.  *----------------------------------------------------------------------
  1256.  *
  1257.  * TclRegError --
  1258.  *
  1259.  *    This procedure is invoked by the regexp code when an error
  1260.  *    occurs.  It saves the error message so it can be seen by the
  1261.  *    code that called Spencer's code.
  1262.  *
  1263.  * Results:
  1264.  *    None.
  1265.  *
  1266.  * Side effects:
  1267.  *    The value of "string" is saved in "tclRegexpError".
  1268.  *
  1269.  *----------------------------------------------------------------------
  1270.  */
  1271.  
  1272. void
  1273. TclRegError(string)
  1274.     char *string;            /* Error message. */
  1275. {
  1276.     tclRegexpError = string;
  1277. }
  1278.